#include <iostream>
using namespace std;
// 堆排序
void AdjustDwon(int* a, int n, int root) {
    int child = root * 2 + 1;
    while(child < n) {
        if(child + 1 < n && a[child + 1] > a[child]) {
            child++;
        }
        if(a[root] >= a[child]) {
            break;
        }
        swap(a[root], a[child]);
        root = child;
        child = root * 2 + 1;
    }
}
void BuildHeap(int* a, int n) {
    for(int i = (n - 2) / 2; i >=0; i--) { // 注意这里是减去2而不是1，这里的n表示的是数组的大小值，不是最后一个位置的下标
        AdjustDwon(a, n, i);
    }
}
void HeapSort(int* a, int n) {
    BuildHeap(a, n);
    for(int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);
        AdjustDwon(a, i, 0);
    }
}
int main() {
    int a[10] = {1, 4, 3, 5, 6, 3, 2, 7, 8, 0};
    HeapSort(a, 10);
    for(int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}